"""
给定二维矩阵与X, 在其中填入不超过X的正整数, X保证是偶数
要求使得每一个2×2的子矩阵之和为偶数，问一共有多少种不同的填法
如果只考虑奇偶，则一个子矩阵一共有8种填法
当固定了左边，往右一列则只剩2种填法, 往下一行同样
无论奇偶，每一个均有X/2种填法，因此连乘起来即可
"""
class Solution:
    def numsOfGoodMatrix(self , n , m , x ):
        MOD = 1000000000 + 7

        def qpow(a, n):
            ret = 1
            while n != 0:
                if n % 2 == 1: ret = ret * a % MOD
                a = a * a % MOD
                n //= 2
            return ret
        
        ans = qpow(x // 2, n * m)
        ans = ans * qpow(2, n - 2) % MOD
        ans = ans * qpow(2, m - 2) % MOD
        ans = ans * 8 % MOD
        return ans